// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include <string.h>
// #include <Windows.h>
//
// #define MAXSIZE 200
//
// typedef struct SString {
//     char ch[MAXSIZE];
//     int length;
// } SString;
//
// // 初始化字符串
// void InitStr(SString* str) {
//     str->length = 0;
//     memset(str->ch, 0, MAXSIZE);
// }
//
// // 字符串赋值操作
// bool StrAssign(SString* str, const char* chars) {
//     if (str == NULL || chars == NULL) {
//         return false;
//     }
//
//     int len = strlen(chars);
//     if (len >= MAXSIZE) {
//         printf("错误：字符串长度超过最大值 %d\n", MAXSIZE);
//         return false;
//     }
//
//     strncpy(str->ch, chars, len);
//     str->ch[len] = '\0';
//     str->length = len;
//     return true;
// }
//
// // 打印字符串
// void PrintStr(const SString* str) {
//     if (str == NULL || str->length == 0) {
//         printf("字符串为空\n");
//         return;
//     }
//     printf("%s\n", str->ch);
// }
//
// // 构造 next 数组
// void get_next(const SString* T, int next[]) {
//     int j = 0;
//     next[0] = 0;
//     for (int i = 1; i < T->length; i++) {
//         while (j > 0 && T->ch[i] != T->ch[j]) {
//             j = next[j - 1];
//         }
//         if (T->ch[i] == T->ch[j]) {
//             j++;
//         }
//         next[i] = j;
//     }
// }
//
// // KMP 查找
// int Index_KMP(const SString* S, const SString* T, int next[]) {
//     int j = 0;
//     for (int i = 0; i < S->length; i++) {
//         while (j > 0 && S->ch[i] != T->ch[j]) {
//             j = next[j - 1];
//         }
//         if (S->ch[i] == T->ch[j]) {
//             j++;
//         }
//         if (j == T->length) {
//             return i - j + 1; // 匹配成功返回位置
//         }
//     }
//     return -1;
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//
//     SString s, t;
//     InitStr(&s);
//     InitStr(&t);
//
//     StrAssign(&s, "abaabaabc");
//     StrAssign(&t, "abaabc");
//
//     int next[MAXSIZE] = {0};
//     get_next(&t, next);
//
//     printf("打印 next 数组: ");
//     for (int i = 0; i < t.length; i++) {
//         printf("%d ", next[i]);
//     }
//     printf("\n");
//
//     int pos = Index_KMP(&s, &t, next);
//     if (pos != -1) {
//         printf("模式串在主串中的位置（从0开始）: %d\n", pos);
//     } else {
//         printf("未找到模式串。\n");
//     }
//
//     return 0;
// }
